Entscheidungsverfahren

Entscheidungsverfahren,

 

mathematische Logik: jedes System von Regeln, mit dessen Hilfe die Entscheidung eines Problems (in Form einer endgültigen Antwort auf eine gestellte Frage) in endlich vielen, nach Regeln des Systems vorgenommenen Schritten gefällt werden kann. Entscheidungsverfahren ermöglichen eine Entscheidung darüber, ob ein bestimmtes Objekt der Wert einer Funktion zu gegebenen Argumenten ist oder ob ein Objekt zu einer bestimmten Menge gehört. - Funktionen, für die es ein Entscheidungsverfahren gibt, heißen »berechenbar«, Mengen, für die Entsprechendes gilt, »entscheidbar«. Ein Begriff heißt entscheidbar oder »definit«, wenn die Menge der unter ihn fallenden Gegenstände entscheidbar ist.

 

Für beliebig, auch quantorenlogisch zusammengesetzte Aussagen ist das Entscheidungsproblem unlösbar, d. h., es gibt kein allgemeines Entscheidungsverfahren, das für jede Aussage über ihre logische Wahrheit zu entscheiden gestattet (»Unentscheidbarkeitssatz« von A. Church, 1936). mathematische Logik.

 

Literatur:

 

W. Stegmüller: Unvollständigkeit u. Unentscheidbarkeit (Wien ³1973);

 G. Boolos u. R. C. Jeffrey: Computability and logic (Cambridge 1974).